package LeetCodeHot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 15. 三数之和
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

    思路：三数之和完全可以简化， 简化为两数之和， 而且三数之和等于0，是不是就可以认为 a + b = -c .
         所以就可以外层固定一个循环，固定c值，然后利用双指针法遍历获取值。
         但这样的话必须排序，才能使用双指针法遍历解决问题。
         这道题也检查了对边界问题，无效循环的考虑。
 */
public class LeetCode15 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums.length<2){
            return result;
        }
        // 排序  O(nlogn)
        Arrays.sort(nums);

        List<Integer> temp = null;

        for (int k = 0; k < nums.length-2; k++) {
            // 考虑剪枝情况，避免无效循环
            if(nums[k] > 0){
                break;
            }
            // 同样值的k元素可以跳过
            if(k>0 && nums[k] == nums[k-1]){
                continue;
            }
            int i = k + 1,j = nums.length-1;
            while (i<j){
                if(nums[i]+nums[j] == -nums[k]){
                    temp = new ArrayList<>();
                    temp.add(nums[i]);
                    temp.add(nums[j]);
                    temp.add(nums[k]);
                    result.add(temp);
                    // 去重操作
                    while ( i < j && nums[i] == nums[++i]);
                    while ( i < j && nums[j] == nums[--j]);
                }else if(nums[i] + nums[j] > -nums[k]){  // j--
                    //去重操作
                    while ( i < j && nums[j] == nums[--j]);
                }else {         // i++
                    while ( i < j && nums[i] == nums[++i]);
                }
            }
        }
        return result;
    }
}
